#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100'000'000;

int lim;
int mu[N + 1];
int tmp[N + 1];
i64 sigma0[N + 1];

std::vector<int> pri;

i64 sum_mu2(i64 n) {
    if (n <= lim) return tmp[n];
    i64 res = 0;
    for (i64 i = 1; i * i <= n; ++i) {
        if (mu[i]) res += mu[i] * (n / (i * i));
    }
    return res;
}

i64 sum_sigma0(i64 n) {
    if (n <= lim) return sigma0[n];
    i64 res = 0;
    i64 i;
    for (i = 1; i * i <= n; ++i) res += n / i;
    --i;
    res = res * 2 - i * i;
    return res;
}

i64 q[10000];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;
    for (int i = 0; i < T; ++i) std::cin >> q[i];
    lim = std::max(int(std::pow(*std::max_element(q, q + T), 2.0 / 3.0)), 10000);

    mu[1] = 1;
    sigma0[1] = 1;
    for (int i = 2; i <= lim; ++i) {
        if (!sigma0[i]) {
            pri.push_back(i);
            mu[i] = -1;
            tmp[i] = 2;
            sigma0[i] = 2;
        }
        for (int j : pri) {
            int k = i * j;
            if (k > lim) break;
            if (i % j != 0) {
                mu[k] = -mu[i];
                tmp[k] = 2;
                sigma0[k] = sigma0[i] * 2;
            } else {
                mu[k] = 0;
                tmp[k] = tmp[i] + 1;
                if (k == tmp[k]) {
                    sigma0[k] = sigma0[i] + 1;
                } else {
                    sigma0[k] = sigma0[i] / tmp[i] * tmp[k];
                }
                break;
            }
        }
    }
    for (int i = 1; i <= lim; ++i) tmp[i] = mu[i] * mu[i] + tmp[i - 1];
    for (int i = 1; i <= lim; ++i) sigma0[i] += sigma0[i - 1];

    for (int i = 0; i < T; ++i) {
        i64 n = q[i];
        i64 ans = 0;
        i64 last = 0;
        for (i64 l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            i64 now = sum_mu2(r);
            ans += (now - last) * sum_sigma0(n / l);
            last = now;
        }
        std::cout << ans << '\n';
    }

    return 0;
}